package com.agile.leetcode.easy.maxSubArray;

/**
 * 剑指 Offer 42. 连续子数组的最大和
 * 输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。
 * <p>
 * 要求时间复杂度为O(n)。
 * <p>
 * <p>
 * <p>
 * 示例1:
 * <p>
 * 输入: nums = [-2,1,-3,4,-1,2,1,-5,4]
 * 输出: 6
 * 解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
 *
 * @Author:ChenZhangKun
 * @Date: 2021/4/4 12:44
 */
public class MaxSubArray {
    public static void main(String[] args) {
        int[] nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        MaxSubArray subArray = new MaxSubArray();
        int i = subArray.maxSubArray(nums);
        System.out.println(i);
    }

    public int maxSubArray(int[] nums) {
        // 拿到数组长度
        int length = nums.length;
        // 创建相同长度数组
        int[] dp = new int[length];
        dp[0] = nums[0];
        // 遍历
        for (int i = 1; i < nums.length; i++) {
            // 状态转移方程
            if (dp[i - 1] > 0) {
                dp[i] = nums[i] + dp[i - 1];
            } else {
                dp[i] = nums[i];
            }
        }
        // 找出最大数
        int max = Integer.MIN_VALUE;
        for (int i : dp) {
            if (i > max) {
                max = i;
            }
        }
        return max;
    }
}
